At present, while regulations on the protection of both private information and confidential information have been strengthened, the market for services using such information is expanding. Encryption techniques capable of using data while keeping private information and confidential information protected have therefore attracted attention. Among encryption techniques, there are ones which use encryption techniques and statistical techniques in accordance with data classification and service requirements.
There is a technique known as a homomorphic encryption scheme, which is a concealment technique using encryption. The homomorphic encryption scheme is a public key encryption scheme such that the encryption key and the decryption key are different, and it is a form of encryption which has a function capable of manipulating data while keeping the data encrypted. For example, assuming that for plain text m1 and m2, the encryption function of a homomorphic encryption scheme for addition or multiplication is given by E, the following expressions (1) or (2) hold.E(m1)+E(m2)=E(m1+m2)  (1)E(m1)*E(m2)=E(m1*m2)  (2)
A property such that expression (1) holds is called a homomorphism for addition, and a property such that expression (2) holds is called a homomorphism for multiplication.
Addition and multiplication of encrypted text (also referred to as “cipher text”) by using a homomorphic encryption scheme makes it possible to obtain an encrypted operation result of addition and multiplication without decrypting the encrypted text. It is expected that the properties of homomorphic encryption will be used in the fields of electronic voting, electronic money, and similar, and furthermore in recent years it has been expected that they will be used in the cloud computing field.
An RSA (Rivest Shamir Adleman) encryption scheme (homomorphism only for multiplication) and an Additive ElGamal encryption scheme (homomorphism only for addition) are typical of such homomorphic encryption schemes. Moreover, a homomorphic encryption scheme which is capable of both addition and multiplication (an encryption scheme satisfying expressions (1) and (2)) was suggested (a technique suggested in Non-Patent Document 1) in 2009. However, it is known that such a homomorphic encryption scheme is not practical in terms of processing performance and the size of encrypted data. A homomorphic encryption scheme which is capable of both addition and multiplication and is practical in terms of both processing performance and the size of encrypted data was therefore suggested in 2011, and the examples of application was suggested (the technique suggested in Non-Patent Document 2).
Here, the homomorphic encryption scheme proposed in 2011 will be explained (for details, see Section 3.2 of Non-Patent Document 2). Firstly, mainly prepare three key generation parameters (n, q, and t) for encryption key generation. n is an integer, it is the power of 2, and it is referred to as a “lattice dimension”; q is a prime number, and t is an integer which is smaller than the prime number q. In the encryption key generation procedure, firstly an n-dimensional polynomial sk such that each of its coefficients is extremely small is randomly generated as a secret key. The smallness of each coefficient is limited by a parameter σ. Next, an n-dimensional polynomial a1 such that each of its coefficients is smaller than q, and an n-dimensional polynomial e such that each of its coefficients is extremely small, are randomly generated.
a0=−(a1*sk+t*e) is calculated, and a pair (a0, a1) is defined as public key pk. However, when the polynomial a0 is calculated, a polynomial whose degree is always less than n is calculated as xn=−1, xn+1=−x, . . . for a polynomial whose degree is n or higher. Furthermore, output the remainder obtained by dividing by the prime number q for the coefficients of the polynomials. The space for performing such an operation is academically expressed as Rq: =Fq[x]/(xn+1).
Next, for public key pk=(a0, a1) and plain text data m which is represented by a polynomial of degree n such that each of its coefficients is smaller than t, three n-dimensional polynomials u, f, and g such that each of their coefficients is extremely small are randomly generated, and encryption data E(m, pk)=(c0, c1) for the plain text data m is defined as follows. For (c0, c1), c0=a0*u+t*g+m, c1=a1*u+t*f is calculated. Also, operation is performed on the space Rq in these calculations.
Thereafter, for the encrypted text E(m1, pk)=(c0, c1) and E(m2, pk)=(d0, d1), encryption addition E(m1, pk)+E(m2, pk) is calculated as (c0+d0, c1+d1), and encryption multiplication E(m1, pk)*E(m2, pk) is calculated as (c0*d0, c0*d1+c1*d0, c1*d1). Note that such encryption multiplication makes data size of the encrypted text change from a 2-component vector to a 3-component vector.
Lastly, in decryption processing, the secret key sk will be used in calculating D(c, sk)=[c0+c1*sk+c2*sk2+ . . . ] q mod t for the encrypted text c=(c0, c1, c2, . . . ) (here, it is assumed that the number of data components of the encrypted text data has increased by encryption operations such as multiple encryption multiplication), to complete decryption. Here, w is calculated as the remainder obtained by dividing the integer z by q, and the value of [z]q is outputted as [z]q=w if w<q and the value of [z]q is outputted as [z]q=w−q if w≧q. Furthermore, “a mod t” means the remainder obtained by dividing the integer a by t.
Numerical examples are illustrated for simplicity's sake in the following.
Secret key sk=Mod(Mod(4, 1033)*x3+Mod (4, 1033)*x2+Mod(1, 1033)*x, x4+1)
Public Key pk=(a0, a1)
a0=Mod(Mod(885, 1033)*x3+Mod(519, 1033)*x2+Mod(621, 1033)*x+Mod(327, 1033), x4, x4+1)
a1=Mod(Mod(661, 1033)*x3+Mod(625, 1033)*x2+Mod(861, 1033)*x+Mod(311, 1033), x4+1)
E(m, pk)=(c0, c1)
Plain text data m=3+2x+2x2+2x3 
c0=Mod(Mod(822, 1033)*x3+Mod(1016, 1033)*x2+Mod(292, 1033)*x+Mod(243, 1033), x4+1)
c1=Mod(Mod(840, 1033)*x3+Mod(275, 1033)*x2+Mod(628, 1033)*x+Mod(911, 1033), x4+1)
In the preceding expressions, (4, 1033, 20) are set to be the key generation parameters (n, q, t). Furthermore, Mod(a, q) means the remainder obtained by dividing integer a by prime number q, and Mod (f (x), x4+1) means a polynomial of the remainder obtained by dividing polynomial f(x) by polynomial x4+1. However, x4=−1, x5=x, . . . and similar hold.
Next, pattern matching will be briefly explained. Pattern matching is, for example, processing which determines whether a pattern string exists in a text string or not. For example, processing which determines whether pattern string P=“abbac” exists in text string T=“acbabbaccb” or not is considered. At this time, as illustrated in FIG. 1, the number of characters (also referred to as the distance) where the text and the pattern coincide is calculated for text string T, as pattern string P is displaced by one character. In FIG. 1, a list of numerical values representing the number of characters is referred to as a “score vector”. In this example, text string T and pattern string P coincide in the component whose score vector value is 5, since the length of pattern string P is 5.
Thus, in pattern matching without encryption, for text string T and pattern string P, the distance between the text string and the pattern string is calculated as pattern string P is displaced by one character at a time.
On the other hand, in secure pattern matching using homomorphic encryption (for example, as in Non-Patent Document 3), a polynomial expressed by using each bit of a binarized text for its coefficients in ascending order of degree is calculated to reduce the data size and distance calculation cost. And the binarized text is encrypted by a homomorphic encryption scheme which is capable of calculating polynomials (for example, homomorphic encryption based on Ring-LWE: see Non-Patent Document 2). On the other hand, a polynomial expressed by using each bit of a binarized pattern for its coefficients in descending order of degree is calculated, and the binarized pattern is encrypted using the same homomorphic encryption scheme.
Thereafter, for the text polynomial and the pattern polynomial which are encrypted by homomorphic encryption, perform encryption operations by using a homomorphism on the polynomials such that each of their coefficients represents a hamming distance between the text and the pattern. Then, identify the hamming distance from each coefficient of polynomials obtained by decrypting the encryption operation result, and determine whether the hamming distance is 0 or not. Secure pattern matching is performed by doing this.
More specifically, from binarized text T=(t0, t1, . . . , tk−1) whose length is k (also called a binary vector), generate polynomial mt(T)=Σitixi using each bit as its coefficients in ascending order, and for this, generate encrypted text Enc(mt(T), pk) by the aforementioned homomorphic encryption scheme. Text T is encrypted by doing so.
On the other hand, from binarized pattern P=(p0, p1, . . . , pl−1) whose length is l, generate polynomial mp(P)=−Σjpjxn−j using each bit as its coefficients in descending order, and generate encrypted pattern Enc(mp(P), pk) by using the aforementioned homomorphic encryption scheme. Pattern P is encrypted by doing so.
Next, for the encrypted text Enc(mt(T), pk) and the encrypted pattern Enc(mp(P), pk), calculate the encryption distance as follows.Enc(mt(T),pk)*C1+Enc(mp(P),pk)*Ck−2Enc(mt(T),pk)*Enc(mp(P),pk)  (3)
Here, C1 is a member which includes a polynomial whose length is l in descending order of degree, and Ck is a member which includes a polynomial whose length is k in ascending order of degree. These are represented as follows.C1=(−Σjxn−j,0)  (4)Ck=(Σixi,0)  (5)
When a result obtained by decrypting an encryption distance calculation result obtained by expression (3) is r0+r1x+r2x2+ . . . +rn−1xn−1 (a polynomial of degree n, whose coefficients are equal to or less than parameter t), the coefficient ri of degree i for 0≦i≦k−1 coincides with hamming distance d (T(i), P) between partial text T(i) whose first part is the i-th bit and pattern P. Therefore, the degree whose coefficient is 0 may be identified to determine which part of text T includes pattern P from the decryption result r0+r1x+r2x2+ . . . +rn−1xn−1. In other words, it becomes possible to calculate text T and pattern P while keeping them encrypted by homomorphic encryption.
Here, an approach to such secure pattern matching is explained by using FIG. 2. The following operation is performed so that each coefficient of a polynomial will correspond to hamming distance d(T(i), P) in the plain text space.Σi(HW(T(i))+HW(P)−2<T(i),P>)xi  (6)
HW(A) represents the hamming weight of A, and <A, B> represents the inner product between A and B.
ΣiHW(T(i)) xi in expression (6) is mt(T)*(−Σixn−j), as illustrated in FIG. 2(A). Moreover, ΣiHW(P) xi in expression (6) is mp(P)*(Σixi), as illustrated in FIG. 2(B). Furthermore, Σi<T(i), P>xi in expression (6) is mt(T)*mp(P), as illustrated in FIG. 2(C).
By doing so, as illustrated in FIGS. 2(A) to 2(C), for each plain text operation, an encryption operation corresponding to the plain text operation is obtained in the encrypted text space. Therefore, as a result, as illustrated in FIG. 2(D), an operation such that the coefficients represent the hamming distance if the polynomials are decrypted is performed by executing the encryption operation as illustrated in expression (3).
However, in performing plain text polynomial operations, output the remainder of division by parameter t, for the coefficients of each polynomial which should be of degree n or less, by calculating a polynomial whose degree is always n or less by calculating xn=−1, xn+1=−x, . . . for polynomials whose degree is n or more. Space for performing such an operation is often represented as Rt=Fq[x]/(xn+1).
However, since it is not considered to treat a special character (called a wild card) corresponding to any character, it is not possible to efficiently perform secure pattern matching using general patterns such as those including wild cards.    Non-Patent Document 1: C. Gentry, “Fully Homomorphic encryption using ideal lattices”, STOC 2009, ACM, pp. 169-178, 2009.    Non-Patent Document 2: K. Lauter, M. Naehrig and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?”, In ACM workshop on Cloud Computing Security Workshop-CCSW 2011, ACM, pp. 113-124, 2011.    Non-Patent Document 3: M. Yasuda, T, Shimoyama, J. Kogure, K. Yokoyama and T. Koshiba, “Secure Pattern Matching using Somewhat Homomorphic Encryption”, CCSW′13, Nov. 8, 2013, pp. 65-76
In other words, there is no technique to increase the general applicability of secure pattern matching.